package day09_链表相关;

/**
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 * 你应当 保留 两个分区中每个节点的初始相对位置。
 *
 * 链接：https://leetcode.cn/problems/partition-list
 *
 */
public class Code03_leetcode_分隔链表 {
    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode lHead = new ListNode(0);
        ListNode lTail = lHead;
        ListNode rHead = new ListNode(0);
        ListNode rTail = rHead;
        while (head != null) {
            if (head.val < x) { // 放在lTail后面
                lTail.next = head;
                lTail = head;
            } else { // 放在rTail后面
                rTail.next = head;
                rTail = head;
            }
            head = head.next;
        }
        // 这句代码不能少
        /*
         * 因为可能出现这样的情况:
         * 原链表倒数第N个节点A的值是>=x的，A后面所有节点的值都是<x的
         * 然后rTail.next最终其实就是A.next
         */
        rTail.next = null;
        // 将rHead.next拼接在lTail后面
        lTail.next = rHead.next;
        return lHead.next;
    }

}
